package com.demo.datastructure.reorder.shellSort;

import com.demo.datastructure.reorder.Example;

/**
 * @author ljr
 * @version 5.0  算法习题2.1.11
 * @description: 希尔排序
 * @date 2021/9/17 21:19
 */
public class MyShellSort5 implements Example {

    @Override
    public void sort(Comparable[] a) {
        int n = a.length;
        int h = 1;
        while(h < n/3)  h = h*3+1;

        int index = 0;
        int[] nums = new int[n/4];

        while(h >= 1){
            nums[index++] = h;
            h /= 3;
        }

        for(int num : nums){
            if(num == 0){
                break;
            }

            int count = 0;
            for(int i = num; i < n; i++){
                for(int j = i; j >= num && (count++ > -1) && less(a[j], a[j - num]); j -= num){
                    exch(a, j, j-num);
                }
            }
            System.out.println("num为===="+num+";比较次数为=========="+count);
        }
    }

}
